[BZOJ1030]-文本生成器

AC自动机, 线性DP

题目链接

如果要计算可读文本的数量，那就要用到容斥（没尝试过。。应该不好算，或者不能算）

不如计算不可读文本数量，再用总数减去它！（这叫逆向思维还是啥

这样就比较美滋滋了，只要不让 AC 自动机上走到单词节点就好了。DP 的话，设 $f[i, j]$ 表示文本长度为 $i$，匹配到自动机上第 $j$ 个节点时的情况数。同时要记得排除一个模式串包含另一个模式串，第一个没走到单词节点，第二个却走到了的情况。代码中也有注释。

Hint！$f[0, 0]$ 也是一种不可读的情况哦，不能舍。

code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

const int N = 6010, M = 110, mod = 10007;
int n, m, sz, ans = 1;
int trie[N][30], f[M][N], fail[N];
bool val[N];
char s[M];
queue<int> q;

int idx(char ch) { return ch - 'A'; }

void insert(char *s) {
    int len = strlen(s);
    int u = 0;
    for (int i = 0; i < len; i++) {
        int c = idx(s[i]);
        if (!trie[u][c]) trie[u][c] = ++sz;
        u = trie[u][c];
    }
    val[u] = 1;
}

void getfail() {
    fail[0] = 0;
    for (int i = 0; i < 26; i++)
        if (trie[0][i]) q.push(trie[0][i]);
    while (!q.empty()) {
        int r = q.front(); q.pop();
        for (int c = 0; c < 26; c++) {
            int u = trie[r][c];
            if (u) {
                fail[u] = trie[fail[r]][c];
                q.push(u);
            } else trie[r][c] = trie[fail[r]][c];
        }
        if (val[fail[r]]) val[r] = 1;  // 这边跟传统的自动机有些不同，是为了不让 “一个模式串包含另一个模式串，一个没走到单词节点但另一个走到了” 的情况出现
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        insert(s);
    }
    getfail();
    f[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= sz; j++) {  // j 从 0 号节点开始！
            if (val[j] || !f[i][j]) continue;  // 只要碰到任意单词节点就不走
            for (int k = 0; k < 26; k++) {
                int u = trie[j][k];
                // 这里 u 即使 == 0 也没有关系！可以理解为文本第 i + 1 个位置与自动机的根结点（0 号节点）匹配
                f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
            }
        }
    }
    for (int i = 0; i < m; i++) ans = ans * 26 % mod;
    for (int i = 0; i <= sz; i++)  // 不要忘记算上 f[0, 0]
        if (!val[i]) // !!!
            ans = (ans + mod - f[m][i]) % mod;
    printf("%d\n", ans);
    return 0;
}